The speed at which a personal computer operates is dependent upon a number of factors. Naturally, the speed of the microprocessor has a significant influence on the speed of operation of the overall computer system. Next to processor speed, in many cases, the video graphics subsystem has the most influence on the performance of the overall computer system. This is particularly true when a graphical user interface, such as MICROSOFT WINDOWS (by Microsoft Corporation of Redmond, Wash.) is used. In order to boost performance, most modern day personal computers use either a local video bus (which has a higher data bandwidth than the main peripheral bus) and an accelerated video card which increases the speed of certain operations. An accelerated video card allows the video card to perform selected video operations at high speed, rather than using the CPU to perform the operation. Hardware acceleration improves the operation of the computer system in two ways: (1) the CPU no longer needs to perform low-level video operations handled by the video card and (2) the data bandwidth for certain operations is greatly reduced, resulting in less bus traffic.
In order for acceleration to increase the responsiveness of the system, the operating environment, such as WINDOWS, must know the capabilities of the accelerated video subsystem. When the operating environment is loaded, it initiates the loading of a video driver, which is a program which acts as an intermediary between the operating environment and accelerated video hardware. The driver passes parameters to the operating environment which specify the accelerated capabilities of the video subsystem. Thereafter, when the operating environment needs to perform a video operation which could benefit from one of the accelerated capabilities, it passes the necessary data to the driver. The driver interprets the information from the operating environment, processes the information and passes data via the bus to the video subsystem. The video subsystem then performs the video operation by writing data to its frame buffer. As the market for accelerated video subsystems has matured, it has become apparent that the speed of the video subsystem is in large part dependent upon the operation of the video driver.
One class of driver functions (or "primitive") which can have a significant affect on the overall speed of the driver involves the polygon functions. WINDOWS supports two polygon primitives: Alternate Fill Polygon() and Winding Fill Polygon(). These primitives are used to draw solid and outline polygon figures. In support of the primitive call, WINDOWS passes information relating to the desired polygon, such as (1) an ordered list of vertices in screen coordinates (the last coordinate may be omitted; if so, the first coordinate is assumed to be the last coordinate as well), pattern information, color information and border information. Based on this information the driver draws the polygon. The speed at which the driver can draw the polygon is dependent upon the efficiency of the code and whether the video board provides hardware support.
In certain instances, it would be beneficial to know if the polygon is convex, and if so, whether the polygon is simple convex. FIG. 1a illustrates a simple convex polygon 10 (defined by vertices 11 and edges 13) and FIG. 1b illustrates a complex convex polygon 12. A simple convex polygon has no intersecting lines, and therefore, a video driver primitive may be able to take advantage of simpler code in performing functions relating to the polygon, such as using a Cohen-Sutherland clipping method for clipping a polygon which is partially outside of a window. Further, certain hardware acceleration features may by exploited by the driver software in instances where the polygon is simple convex.
A method of determining whether a polygon is convex is described in "Procedural Elements for Computer Graphics" by David F. Rogers, pages 146-151 (McGraw-Hill 1985). This text provides two methods for determining if a polygon is convex. However, the first method (computing and comparing the cross products of adjacent edges of the polygon) does not accurately identify the distinction between simple and complex convex polygons. A second method described in the reference cited above, involves repeatedly translating the polygon such that the ith vertex is positioned on an origin and rotating the polygon about the origin to place the (i+1)th vertex is on the positive x-axis. After the rotation, the sign of the y component of the (i+2)th vertex is noted. This procedure is repeated for each vertex. While the translation steps can be done at high speed, the rotation steps are time consuming due to sine and cosine computations. Thus, while this second method can correctly identify the distinction between simple and complex convex polygons, the slowness of the method when implemented in the driver software makes it undesirable.
Therefore, a need has arisen in the industry for a method and apparatus for determining whether a polygon is a simple convex polygon.